/*
 * fontconfig/src/fclist.c
 *
 * Copyright © 2000 Keith Packard
 *
 * Permission to use, copy, modify, distribute, and sell this software and its
 * documentation for any purpose is hereby granted without fee, provided that
 * the above copyright notice appear in all copies and that both that
 * copyright notice and this permission notice appear in supporting
 * documentation, and that the name of the author(s) not be used in
 * advertising or publicity pertaining to distribution of the software without
 * specific, written prior permission.  The authors make no
 * representations about the suitability of this software for any purpose.  It
 * is provided "as is" without express or implied warranty.
 *
 * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
 * EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY SPECIAL, INDIRECT OR
 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
 * PERFORMANCE OF THIS SOFTWARE.
 */

#include "fcint.h"

#include <stdlib.h>

FcObjectSet *
FcObjectSetCreate (void)
{
    FcObjectSet *os;

    os = (FcObjectSet *)malloc (sizeof (FcObjectSet));
    if (!os)
	return 0;
    os->nobject = 0;
    os->sobject = 0;
    os->objects = 0;
    return os;
}

FcBool
FcObjectSetAdd (FcObjectSet *os, const char *object)
{
    int          s;
    const char **objects;
    int          high, low, mid, c;

    if (os->nobject == os->sobject) {
	s = os->sobject + 4;
	if (os->objects)
	    objects = (const char **)realloc ((void *)os->objects,
	                                      s * sizeof (const char *));
	else
	    objects = (const char **)malloc (s * sizeof (const char *));
	if (!objects)
	    return FcFalse;
	os->objects = objects;
	os->sobject = s;
    }
    high = os->nobject - 1;
    low = 0;
    mid = 0;
    c = 1;
    object = strdup (object);
    while (low <= high) {
	mid = (low + high) >> 1;
	c = os->objects[mid] - object;
	if (c == 0) {
	    FcFree (object);
	    return FcTrue;
	}
	if (c < 0)
	    low = mid + 1;
	else
	    high = mid - 1;
    }
    if (c < 0)
	mid++;
    memmove ((void*)(os->objects + mid + 1), os->objects + mid,
             (os->nobject - mid) * sizeof (const char *));
    os->objects[mid] = object;
    os->nobject++;
    return FcTrue;
}

void
FcObjectSetDestroy (FcObjectSet *os)
{
    int i;

    if (os) {
	if (os->objects) {
	    for (i = 0; i < os->nobject; i++)
		FcFree (os->objects[i]);

	    free ((void *)os->objects);
	}
	free (os);
    }
}

FcObjectSet *
FcObjectSetVaBuild (const char *first, va_list va)
{
    FcObjectSet *ret;

    FcObjectSetVapBuild (ret, first, va);
    return ret;
}

FcObjectSet *
FcObjectSetBuild (const char *first, ...)
{
    va_list      va;
    FcObjectSet *os;

    va_start (va, first);
    FcObjectSetVapBuild (os, first, va);
    va_end (va);
    return os;
}

/*
 * Font must have a containing value for every value in the pattern
 */
static FcBool
FcListValueListMatchAny (FcValueListPtr patOrig, /* pattern */
                         FcValueListPtr fntOrig) /* font */
{
    FcValueListPtr pat, fnt;

    for (pat = patOrig; pat != NULL; pat = FcValueListNext (pat)) {
	for (fnt = fntOrig; fnt != NULL; fnt = FcValueListNext (fnt)) {
	    /*
	     * make sure the font 'contains' the pattern.
	     * (OpListing is OpContains except for strings
	     *  where it requires an exact match)
	     */
	    if (FcConfigCompareValue (&fnt->value,
	                              FC_OP (FcOpListing, FcOpFlagIgnoreBlanks),
	                              &pat->value))
		break;
	}
	if (fnt == NULL)
	    return FcFalse;
    }
    return FcTrue;
}

static FcBool
FcListValueListEqual (FcValueListPtr v1orig,
                      FcValueListPtr v2orig)
{
    FcValueListPtr v1, v2;

    for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext (v1)) {
	for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext (v2))
	    if (FcValueEqual (FcValueCanonicalize (&(v1)->value),
	                      FcValueCanonicalize (&(v2)->value)))
		break;
	if (v2 == NULL)
	    return FcFalse;
    }
    for (v2 = v2orig; v2 != NULL; v2 = FcValueListNext (v2)) {
	for (v1 = v1orig; v1 != NULL; v1 = FcValueListNext (v1))
	    if (FcValueEqual (FcValueCanonicalize (&v1->value),
	                      FcValueCanonicalize (&v2->value)))
		break;
	if (v1 == NULL)
	    return FcFalse;
    }
    return FcTrue;
}

static FcBool
FcListPatternEqual (FcPattern   *p1,
                    FcPattern   *p2,
                    FcObjectSet *os)
{
    int           i;
    FcPatternElt *e1, *e2;

    for (i = 0; i < os->nobject; i++) {
	e1 = FcPatternObjectFindElt (p1, FcObjectFromName (os->objects[i]));
	e2 = FcPatternObjectFindElt (p2, FcObjectFromName (os->objects[i]));
	if (!e1 && !e2)
	    continue;
	if (!e1 || !e2)
	    return FcFalse;
	if (!FcListValueListEqual (FcPatternEltValues (e1),
	                           FcPatternEltValues (e2)))
	    return FcFalse;
    }
    return FcTrue;
}

/*
 * FcTrue iff all objects in "p" match "font"
 */

FcBool
FcListPatternMatchAny (const FcPattern *p,
                       const FcPattern *font)
{
    int i;

    if (!p)
	return FcFalse;
    for (i = 0; i < p->num; i++) {
	FcPatternElt *pe = &FcPatternElts (p)[i];
	FcPatternElt *fe;

	if (pe->object == FC_NAMELANG_OBJECT) {
	    /* "namelang" object is the alias object to change "familylang",
	     * "stylelang" and "fullnamelang" object all together. it won't be
	     * available on the font pattern. so checking its availability
	     * causes no results. we should ignore it here.
	     */
	    continue;
	}
	fe = FcPatternObjectFindElt (font, pe->object);
	if (!fe)
	    return FcFalse;
	if (!FcListValueListMatchAny (FcPatternEltValues (pe),  /* pat elts */
	                              FcPatternEltValues (fe))) /* font elts */
	    return FcFalse;
    }
    return FcTrue;
}

static FcChar32
FcListMatrixHash (const FcMatrix *m)
{
    int xx = (int)(m->xx * 100),
	xy = (int)(m->xy * 100),
	yx = (int)(m->yx * 100),
	yy = (int)(m->yy * 100);

    return ((FcChar32)xx) ^ ((FcChar32)xy) ^ ((FcChar32)yx) ^ ((FcChar32)yy);
}

static FcChar32
FcListValueHash (FcValue *value)
{
    FcValue v = FcValueCanonicalize (value);
    switch (v.type) {
    case FcTypeUnknown:
    case FcTypeVoid:
	return 0;
    case FcTypeInteger:
	return (FcChar32)v.u.i;
    case FcTypeDouble:
	return (FcChar32)(int)v.u.d;
    case FcTypeString:
	return FcStrHashIgnoreCase (v.u.s);
    case FcTypeBool:
	return (FcChar32)v.u.b;
    case FcTypeMatrix:
	return FcListMatrixHash (v.u.m);
    case FcTypeCharSet:
	return FcCharSetCount (v.u.c);
    case FcTypeFTFace:
	return (intptr_t)v.u.f;
    case FcTypeLangSet:
	return FcLangSetHash (v.u.l);
    case FcTypeRange:
	return FcRangeHash (v.u.r);
    }
    return 0;
}

static FcChar32
FcListValueListHash (FcValueListPtr list)
{
    FcChar32 h = 0;

    while (list != NULL) {
	h = h ^ FcListValueHash (&list->value);
	list = FcValueListNext (list);
    }
    return h;
}

static FcChar32
FcListPatternHash (FcPattern   *font,
                   FcObjectSet *os)
{
    int           n;
    FcPatternElt *e;
    FcChar32      h = 0;

    for (n = 0; n < os->nobject; n++) {
	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[n]));
	if (e)
	    h = h ^ FcListValueListHash (FcPatternEltValues (e));
    }
    return h;
}

typedef struct _FcListBucket {
    struct _FcListBucket *next;
    FcChar32              hash;
    FcPattern            *pattern;
} FcListBucket;

#define FC_LIST_HASH_SIZE 4099

typedef struct _FcListHashTable {
    int           entries;
    FcListBucket *buckets[FC_LIST_HASH_SIZE];
} FcListHashTable;

static void
FcListHashTableInit (FcListHashTable *table)
{
    table->entries = 0;
    memset (table->buckets, '\0', sizeof (table->buckets));
}

static void
FcListHashTableCleanup (FcListHashTable *table)
{
    int           i;
    FcListBucket *bucket, *next;

    for (i = 0; i < FC_LIST_HASH_SIZE; i++) {
	for (bucket = table->buckets[i]; bucket; bucket = next) {
	    next = bucket->next;
	    FcPatternDestroy (bucket->pattern);
	    free (bucket);
	}
	table->buckets[i] = 0;
    }
    table->entries = 0;
}

static int
FcGetDefaultObjectLangIndex (FcPattern *font, FcObject object, const FcChar8 *lang)
{
    FcPatternElt  *e = FcPatternObjectFindElt (font, object);
    FcValueListPtr v;
    FcValue        value;
    int            idx = -1;
    int            defidx = -1;
    int            i;

    if (e) {
	for (v = FcPatternEltValues (e), i = 0; v; v = FcValueListNext (v), ++i) {
	    value = FcValueCanonicalize (&v->value);

	    if (value.type == FcTypeString) {
		FcLangResult res = FcLangCompare (value.u.s, lang);
		if (res == FcLangEqual)
		    return i;

		if (res == FcLangDifferentCountry && idx < 0)
		    idx = i;
		if (defidx < 0) {
		    /* workaround for fonts that has non-English value
		     * at the head of values.
		     */
		    res = FcLangCompare (value.u.s, (FcChar8 *)"en");
		    if (res == FcLangEqual)
			defidx = i;
		}
	    }
	}
    }

    return (idx > 0) ? idx : (defidx > 0) ? defidx
                                          : 0;
}

static FcBool
FcListAppend (FcListHashTable *table,
              FcPattern       *font,
              FcObjectSet     *os,
              const FcChar8   *lang)
{
    int            o;
    FcPatternElt  *e;
    FcValueListPtr v;
    FcChar32       hash;
    FcListBucket **prev, *bucket;
    int            familyidx = -1;
    int            fullnameidx = -1;
    int            styleidx = -1;
    int            defidx = 0;
    int            idx;

    hash = FcListPatternHash (font, os);
    for (prev = &table->buckets[hash % FC_LIST_HASH_SIZE];
         (bucket = *prev); prev = &(bucket->next)) {
	if (bucket->hash == hash &&
	    FcListPatternEqual (bucket->pattern, font, os))
	    return FcTrue;
    }
    bucket = (FcListBucket *)malloc (sizeof (FcListBucket));
    if (!bucket)
	goto bail0;
    bucket->next = 0;
    bucket->hash = hash;
    bucket->pattern = FcPatternCreate();
    if (!bucket->pattern)
	goto bail1;

    for (o = 0; o < os->nobject; o++) {
	if (!strcmp (os->objects[o], FC_FAMILY) || !strcmp (os->objects[o], FC_FAMILYLANG)) {
	    if (familyidx < 0)
		familyidx = FcGetDefaultObjectLangIndex (font, FC_FAMILYLANG_OBJECT, lang);
	    defidx = familyidx;
	} else if (!strcmp (os->objects[o], FC_FULLNAME) || !strcmp (os->objects[o], FC_FULLNAMELANG)) {
	    if (fullnameidx < 0)
		fullnameidx = FcGetDefaultObjectLangIndex (font, FC_FULLNAMELANG_OBJECT, lang);
	    defidx = fullnameidx;
	} else if (!strcmp (os->objects[o], FC_STYLE) || !strcmp (os->objects[o], FC_STYLELANG)) {
	    if (styleidx < 0)
		styleidx = FcGetDefaultObjectLangIndex (font, FC_STYLELANG_OBJECT, lang);
	    defidx = styleidx;
	} else
	    defidx = 0;

	e = FcPatternObjectFindElt (font, FcObjectFromName (os->objects[o]));
	if (e) {
	    for (v = FcPatternEltValues (e), idx = 0; v;
	         v = FcValueListNext (v), ++idx) {
		if (!FcPatternAdd (bucket->pattern,
		                   os->objects[o],
		                   FcValueCanonicalize (&v->value), defidx != idx))
		    goto bail2;
	    }
	}
    }
    *prev = bucket;
    ++table->entries;

    return FcTrue;

bail2:
    FcPatternDestroy (bucket->pattern);
bail1:
    free (bucket);
bail0:
    return FcFalse;
}

FcFontSet *
FcFontSetList (FcConfig    *config,
               FcFontSet  **sets,
               int          nsets,
               FcPattern   *p,
               FcObjectSet *os)
{
    FcFontSet      *ret;
    FcFontSet      *s;
    int             f;
    int             set;
    FcListHashTable table;
    int             i;
    FcListBucket   *bucket;
    int             destroy_os = 0;

    if (!config) {
	if (!FcInitBringUptoDate())
	    goto bail0;
    }
    config = FcConfigReference (config);
    if (!config)
	goto bail0;
    FcListHashTableInit (&table);

    if (!os) {
	os = FcObjectGetSet();
	destroy_os = 1;
    }

    /*
     * Walk all available fonts adding those that
     * match to the hash table
     */
    for (set = 0; set < nsets; set++) {
	s = sets[set];
	if (!s)
	    continue;
	for (f = 0; f < s->nfont; f++)
	    if (FcListPatternMatchAny (p,            /* pattern */
	                               s->fonts[f])) /* font */
	    {
		FcChar8 *lang;

		if (FcPatternObjectGetString (p, FC_NAMELANG_OBJECT, 0, &lang) != FcResultMatch) {
		    lang = FcGetDefaultLang();
		}
		if (!FcListAppend (&table, s->fonts[f], os, lang))
		    goto bail1;
	    }
    }
#if 0
    {
	int	max = 0;
	int	full = 0;
	int	ents = 0;
	int	len;
	for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	{
	    if ((bucket = table.buckets[i]))
	    {
		len = 0;
		for (; bucket; bucket = bucket->next)
		{
		    ents++;
		    len++;
		}
		if (len > max)
		    max = len;
		full++;
	    }
	}
	printf ("used: %d max: %d avg: %g\n", full, max,
		(double) ents / FC_LIST_HASH_SIZE);
    }
#endif
    /*
     * Walk the hash table and build
     * a font set
     */
    ret = FcFontSetCreate();
    if (!ret)
	goto bail1;
    for (i = 0; i < FC_LIST_HASH_SIZE; i++)
	while ((bucket = table.buckets[i])) {
	    if (!FcFontSetAdd (ret, bucket->pattern))
		goto bail2;
	    table.buckets[i] = bucket->next;
	    free (bucket);
	}

    if (destroy_os)
	FcObjectSetDestroy (os);
    FcConfigDestroy (config);

    return ret;

bail2:
    FcFontSetDestroy (ret);
bail1:
    FcListHashTableCleanup (&table);
    FcConfigDestroy (config);
bail0:
    if (destroy_os)
	FcObjectSetDestroy (os);
    return 0;
}

FcFontSet *
FcFontList (FcConfig    *config,
            FcPattern   *p,
            FcObjectSet *os)
{
    FcFontSet *sets[2], *ret;
    int        nsets;

    if (!config) {
	if (!FcInitBringUptoDate())
	    return 0;
    }
    config = FcConfigReference (config);
    if (!config)
	return NULL;
    nsets = 0;
    if (config->fonts[FcSetSystem])
	sets[nsets++] = config->fonts[FcSetSystem];
    if (config->fonts[FcSetApplication])
	sets[nsets++] = config->fonts[FcSetApplication];
    ret = FcFontSetList (config, sets, nsets, p, os);
    FcConfigDestroy (config);

    return ret;
}
#define __fclist__
#include "fcaliastail.h"
#undef __fclist__
